package arithmetic1.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/*
    插入排序:
        将待排序列分成两个子序列：一个有序序列和一个无序序列，有序序列初始化长度为1，无序序列初始化长度为length-1
        每次取无序序列的第一个元素，来跟有序序列作比较，将其插入到适当的位置,让后有序序列长度+1 无序序列长度-1
        直到无序序列长度为0为止
 */
public class InsertSort {
    public static void main(String[] args) {
//        int arr[]={6,1,68,3,9,32};
        int arr[] = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }

        Date date = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String time1 = sdf.format(date);
        System.out.println("排序前的时间:" + time1);

        insertSort(arr);

        date = new Date();
        String time2 = sdf.format(date);
        System.out.println("排序后的时间:" + time2);

//        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            //记录要插入的数
            int temp = arr[i + 1];
            //记录要掺入的位置, 默认为它本身的位置
            int index = i + 1;
            for (int j = i; j >= 0; j--) {
                if (temp < arr[j]) {
                    //将大的数后移
                    arr[j + 1] = arr[j];
                    //下标前移
                    index--;
                } else {
                    break;
                }
            }
            //将待插入的数插入到index这个位置
            arr[index] = temp;
        }
    }

}
